/**
 * 手动实现二叉树：
 * （1）利用数组存储数据特点：添加，删除数据并不如链表快，但是利用插值算法等，查找数据的索引速度比链表快
 * （2）利用链表存储数据特点：添加，删除数据速度比数组快，但是查找数据的索引速度不如数组
 * （3）二叉树存储数据特点：添加，删除，查找数据速度都比较快,底层有点类似双链表机制
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建节点元素
        Person root = new Person(1, "宋江");//根节点
        Person node2 = new Person(2, "吴用");
        Person node3 = new Person(3, "卢俊义");
        Person node4 = new Person(4, "林冲");
        Person node5 = new Person(5, "关胜");
        //将节点联系起来，拼接成一个二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        //再将根节点赋给二叉树
        binaryTree.setRoot(root);

        //调用二叉树的前序遍历，打印二叉树
        binaryTree.preOrder();  //1,2,3,5,4
        System.out.println("--------------------------");

        //调用二叉树的中序遍历，打印二叉树
        binaryTree.infixOrder();    //2,1,5,3,4
        System.out.println("--------------------------");

        //调用二叉树的后序遍历，打印二叉树
        binaryTree.postOrder();   //2,5,4,3,1
        System.out.println("--------------------------");

        //调用二叉树的前序查找算法
        int num = 5;
        //调用前序查找算法
//        Person person = binaryTree.preOrderSearch(num);
        //调用中序查找算法
//        Person person = binaryTree.infixOrderSearch(num);
        //调用后序查找算法
        Person person = binaryTree.postOrderSearch(num);

        if (person == null) {
            System.out.println("二叉树中，不存在这个值！");
        }else {
            System.out.println(person);
        }
        System.out.println("--------------------------");

        System.out.println("删除前二叉树：");
        binaryTree.preOrder();
        //调用删除节点方法
        binaryTree.delNode(5);
        System.out.println("删除后二叉树：");
        binaryTree.preOrder();  //前序输出：1，2，3，4

    }
}

//创建二叉树，二叉树中也需要具备前中后排序方法
class BinaryTree {
    //创建一个根节点，必须被初始化，可以是在构造方法中初始化
    private Person root;

    public BinaryTree() {
    }

    public BinaryTree(Person root) {
        this.root = root;
    }

    public Person getRoot() {
        return root;
    }

    public void setRoot(Person root) {
        this.root = root;
    }

    //创建前序遍历方法，打印整个二叉树的方法
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建中序遍历方法，打印整个二叉树的方法
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建后序遍历方法，打印整个二叉树的方法
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建前序查找算法:根据用户id查找
    public Person preOrderSearch(int id){
        if (root != null) {
            return root.preOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建中序查找算法:根据用户id查找
    public Person infixOrderSearch(int id){
        if (root != null) {
            return root.infixOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建后序查找算法:根据用户id查找
    public Person postOrderSearch(int id){
        if (root != null) {
            return root.postOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建删除节点的方法
    // 递归删除节点的要求：
    // 1 如果删除的节点是叶子节点 ,则删除该节点
    // 2 如果是非叶子节点 则删除该子树
    // 3 需要找到待删除节点的上一个节点，进行判断，因为二叉树是单向的，所以不能直接找当前节点进行判断
    public void delNode(int id){
        if (root != null) {
            if (root.getId() == id) {//删除的是根节点，直接判断返回
                root = null;
                return;
            }
            root.delNode(id);
        }else {
            System.out.println("根节点为空，没有数据可以删除！");
        }
    }

}

//创建添加到二叉树的节点元素，必须具备前中后三序排序方法
class Person {
    private int id;
    private String name;
    private Person left;     //默认null
    private Person right;    //默认null

    public Person() {
    }

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    //创建前序遍历方法
    public void preOrder() {
        //1.先输出根节点
        System.out.println(this);
        //2.若存在左子节点，则再递归遍历左子节点
        if (this.left != null) {
            this.left.preOrder();
        }
        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //创建中序遍历方法
    public void infixOrder() {
        //1.若存在左子节点，则先递归遍历左子节点
        if (this.left != null) {
            this.left.infixOrder();
        }
        //2.先输出根节点
        System.out.println(this);
        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //创建后序遍历方法
    public void postOrder() {
        //1.若存在左子节点，则先递归遍历左子节点
        if (this.left != null) {
            this.left.postOrder();
        }
        //2.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.postOrder();
        }
        //3.先输出根节点
        System.out.println(this);
    }

    //创建前序查找算法：根据用户id
    public Person preOrderSearch(int id){
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            return res = this;
        }

        //2.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.preOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.preOrderSearch(id);
        }
        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;

    }

    //创建中序查找算法：根据用户id
    public Person infixOrderSearch(int id) {
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.infixOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //2.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            return res = this;
        }

        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.infixOrderSearch(id);
        }
        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;
    }

    //创建后序查找算法：根据用户id
    public Person postOrderSearch(int id) {
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.infixOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //2.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.infixOrderSearch(id);
        }
        //判断右子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //3.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            res = this;
        }

        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;
    }

    //创建删除子节点的方法
    // 递归删除节点的要求：
    // 1 如果删除的节点是叶子节点 ,则删除该节点
    // 2 如果是非叶子节点 则删除该子树
    // 3 需要找到待删除节点的上一个节点，进行判断，因为二叉树是单向的，所以不能直接找当前节点进行判断
    public void delNode(int id){
        //从根节点开始
        //1.先判断左子节点是否是被删除数
        if (this.left != null && this.left.id == id) {
            this.left = null;//将左子节点置空，就是删除左子节点
            return;//结束该方法
        }
        //2.再判断右子节点是否是被删除数
        if (this.right != null && this.right.id == id) {
            this.right = null;//将右子节点置空，就是删除左子节点
            return;
        }
        //3.根节点的左右子节点都不是被删除数，则先向左递归删除
        if (this.left != null) {//若节点下面还有子节点
            this.left.delNode(id);
        }
        //4.根节点的所有左子节点都不是被删除数，则再向右递归删除
        if (this.right != null) {
            this.right.delNode(id);
        }
    }
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Person getLeft() {
        return left;
    }

    public void setLeft(Person left) {
        this.left = left;
    }

    public Person getRight() {
        return right;
    }

    public void setRight(Person right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

}